package 二叉树;

import java.util.*;

public class inorderTraveral {
    // 创建一个TreeNode类
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    // 中序遍历，递归版本
    // 创建一个List，用于存储结果
    static List<Integer> res1 = new ArrayList<>();
    public static List<Integer> inorderTraversal1(TreeNode root) {
        dfs(root);
        return res1;
    }
    // 创建一个dfs方法，用于递归遍历
    public static void dfs(TreeNode root) {
        // 如果根节点为空，则返回
        if(root == null) return;
        // 递归遍历左子树
        dfs(root.left);
        // 将根节点的值加入到结果列表中
        res1.add(root.val);
        // 递归遍历右子树
        dfs(root.right);
    }
    // 中序遍历，迭代版本
    // 采用迭代写法，需要借助栈结构来实现
    // 前序遍历；出栈顺序：根-左-右；入栈顺序：右-左-根；
    // 中序遍历；出栈顺序：左-根-右；入栈顺序：右-根-左；
    // 后序遍历；出栈顺序：左-右-根；入栈顺序：根-右-左；
    public static List<Integer> inorderTraversal2(TreeNode root) {
        // 创建一个List，用于存储结果
        List<Integer> res2 = new ArrayList<>();
        // 创建一个栈，用于存储节点
        Stack<TreeNode> stack = new Stack<>();
        // 当前节点为空或者栈空时，结束循环
        /*
            从单个节点视角来看，每个节点所做的事情都是一样的。
            1.首先先将自己压入栈底，然后不断将左子节点压入栈中，直到左子节点为空。
            2.然后弹出栈顶元素，也就是左子树为空的节点，将该节点的值添加到结果中；
            3.最后将当前节点赋值为该节点的右子节点，然后重复外层循环；
         */
        // tip：阿迪达斯经典logo，三条杠
        while(root != null || !stack.isEmpty()) {
            // 1.先将当前节点的根和其左子树的所有左子节点压入栈中
            while(root != null) {
                // 将根节点入栈
                stack.push(root);
                // 将根节点指向左子树
                root = root.left;
            }
            // 代码执行到此处，当前root节点为空，说明步骤1的root必定没有左子树；
            // 2.此时弹出的栈顶元素，也就是左子树为空的节点，我们暂且叫做：节点t；
            root = stack.pop();
            // 3.将节点值加入到结果列表中
            res2.add(root.val);
            // 4.将当前节点赋值为节点t的右子节点，然后重复外层循环；
            root = root.right;
        }
        // 返回结果列表
        return res2;
    }
    // 建树
    public static TreeNode buildTree(String[] nodes) {
        // 如果节点为空，返回null
        if(nodes == null || nodes.length == 0 || nodes[0].equals("null"))
            return null;
        
        // 创建根节点
        TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
        // 创建一个队列，用于存储节点
        Queue<TreeNode> queue = new LinkedList<>();
        // 将根节点加入队列
        queue.offer(root);

        // 遍历节点
        int index = 1;
        while(!queue.isEmpty() && index < nodes.length) {
            // 取出队列中的节点
            TreeNode cur = queue.poll();
            // 如果当前节点不为空，则将左子节点加入队列
            if(index < nodes.length && !nodes[index].equals("null")) {
                // 创建左子节点
                cur.left = new TreeNode(Integer.parseInt(nodes[index]));
                // 将左子节点加入队列
                queue.offer(cur.left);
            }
            // 索引加1
            index++;
            // 如果当前节点不为空，则将右子节点加入队列
            if(index < nodes.length && !nodes[index].equals("null")) {
                // 创建右子节点
                cur.right = new TreeNode(Integer.parseInt(nodes[index]));
                // 将右子节点加入队列
                queue.offer(cur.right);
            }
            // 索引加1
            index++;
        }
        // 返回根节点
        return root;
    }
    // 主方法
    public static void main(String[] args) {
        // 输入
        Scanner sc = new Scanner(System.in);
        // 输入节点，以空格分隔
        String s = sc.nextLine();
        String[] nodes = s.split(" ");
        // 建树
        TreeNode root = buildTree(nodes);
        // 中序遍历，递归版本
        System.out.println(inorderTraversal1(root));
        // 中序遍历，迭代版本
        System.out.println(inorderTraversal2(root));
        // 关闭Scanner
        sc.close();
    }
}
